Abstract

我是阿傑，昨天 (Day 26) 介紹了 splice() 的基本用法，今天就來介紹 ECMAScript 演算法的部分，這邊會用我的理解將其拆成幾個部份，應該可以稍微減少閱讀的負擔。

最後也利用 ECMAScript 的演算法做了一個非常簡易的客製版 splice()。

ECMAScript

• ECMA 連結 - Array.prototype.splice
• 語法 - Array.prototype.splice(start, deleteCount,...items)

這裡會將整個演算法分成以下幾個部分：

• 參數及基本配置 (步驟 1 ~ 11)
• 刪除元素的陣列處理 (步驟 12 ~ 15)
• 元素向左偏移 (步驟 16)
• 元素向右偏移 (步驟 17)
• 將欲添加元素放入陣列 (步驟 18 ~ 19)
• 收尾 (步驟 20 ~ 21)
• 注意事項

參數及基本配置 (1 ~ 11)

splice() 的演算法並沒有要求呼叫它的一定要是一個陣列，可以從步驟 1 跟 Note 3 得知，為了方便解釋，這邊一律使用陣列來說明；我們來驗證一下它是否被做成了一個通用的咩色：

const fakeArray = {
	0: 0,
	1: 1,
	2: 2,
	length: 3
}

Array.prototype.splice.call(fakeArray, 1, 1)

console.log(fakeArray)
// {0: 0, 1: 2, length: 2}

步驟 3 使用了 ToIntegerOrInfinity() 將 strat 會轉成一個正整數，這個抽象操作比較特別的地方落在了其步驟 5，它對 number 使用了絕對值 (abs()) 後再 floor()，因此 number 的結果會跟預期的不同，例如 1.1 -> 1、-1.1 -> -1。

步驟 5 可以看到當 start 小於 0 時會被加上陣列的長度，如果還是小於 0 則會使用 0 ，驗證了我們前面對參數的說明。

步驟 6 可以看到當 start 大於 0 且大於陣列長度時，會使用陣列長度作為 start。

步驟 8 表明了如果我們沒有提供 start ，則不會有任何元素被刪除。

步驟 9 可以看到如果我們有提供 start 而未提供 deleteCount，那從 start (包括 start) 之後的元素都將被刪除。

步驟 10-b 很有趣，這邊使用了一個特別的描述句 (phrase)，clamping dc between 0 and len - actualStart，這表示 dc 的值會被固定在 0 跟 len - actualStart 之間，因此 deleteCount 最後不會小於 0 或大於 len - actualStart，這很合理，因為我們刪除元素的數量本來就不會小於 0 或者多於可以被刪除的元素數量。

步驟 11 是為了讓修改後的陣列長度仍須維持在安全範圍內，也就是在 JavaScript 的 safe integer 內 (2^53 - 1)。

刪除元素的陣列處理 (12 ~ 15)

步驟 12 我個人認為非常特別，這邊使用 ArraySpeciesCreate() 這個抽象操作來創造一個新陣列，而非直接創造一個新陣列，我們來看一下它做了什麼：

• 它是利用一個陣列 (originalArray) 來作為創造新陣列的依據
• 如果 originalArray 不是一個陣列，則直接使用 ArrayCreat() 來創造新陣列
• 如果 originalArray 是一個陣列，則利用它 constructor 來創造新陣列
• 如果 originalArray 的 constructor 是一個物件，則取出它的一個 well-known Symbol - @@species 屬性，也會拿到一個 constructor，最後還是利用這個 constructor 創造新陣列
• 如果還是取不到 constructor 則直接使用 ArrayCreate() 創造新陣列
  簡而言之，ArraySpeciesCreate() 如果沒有使用 original array 的 constructor，就會使用 ArrayCreate() 來創建一個新陣列。

步驟 14 則是使用將欲刪除的元素加入新陣列中，因為在這之前便已確立了真正的起始位置 actualStart 跟實際會刪除的元素數量 actualDeleteCount，因此可以正確地使用迴圈將欲刪除區間的元素加入新陣列中，而步驟 15 更新了新陣列的長度。

而真正開始修改陣列內容則是從步驟 16 開始，可以分成 3 個部份：

• 當添加元素數量小於刪除元素數量 (2 擇 1) - 步驟 16
• 當添加元素數量大於刪除元素數量 (2 擇 1) - 步驟 17
• 添加元素 - 步驟 19

元素向左偏移 (16)

我們先來解析步驟 16：

• 當添加元素數量小於刪除元素數量時，代表陣列長度會減少，且某區間的元素會向左偏移
• 這邊會先處理元素偏移的部份，首先計算出元素偏移的次數，也代表著迴圈該有的次數 - k < (len - actualDeleteCount)
• 每次迴圈都會利用 from 跟 to 2 個變數來進行取值跟賦值，將元素偏移到新的位置上
• 元素偏移完後便計算出最後該刪除多少元素，再從陣列結尾刪除多餘的元素

元素向右偏移 (17)

反之則會執行步驟 17:

• 當添加元素數量大於刪除元素數量時，代表陣列長度會增加，且某區間的元素會向右偏移
• 這邊會先處理元素偏移的部份，首先計算出元素偏移的次數，也代表著迴圈該有的次數 - k > actualDeleteCount
• 每次迴圈都會利用 from 跟 to 2 個變數來進行取值跟賦值，將元素偏移到新的位置上
• 因為陣列長度增加且元素是向右偏移，所以不需要再刪除多餘的元素

將欲添加元素放入陣列 ( 18 ~ 19)

不論元素是否偏移，都會執行步驟 18 ~ 19，也就是將欲添加的元素從 start 放進陣列中。

收尾 (20 ~ 21)

步驟 20 則會將原陣列設為最後應有的正確長度。

步驟 21 則將包含刪除元素的新陣列回傳出去。

注意事項

在偏移的過程中，每次都會使用 HasProperty() 來檢查 from 是否存在，如果不存在表示其為 empty slot ，所以當次不會執行偏移，而是將 to 直接刪除，而最後陣列會再依據長度將其填充為 empty slot，這是陣列物件的一個特性，我們會於 Day 30 再做介紹。

出現 ? 的地方代表有可能會丟出錯誤，所以整個演算法有 17 處有機會丟出錯誤，例如步驟 16-b-iv 的 DeletePropertyOrThrow() 會在屬性刪除失敗時丟出一個 TypeError；或者步驟 1 的 ToObject() 會在 this 是一個 Undefined 或 Null 時丟出一個 TypeError 的錯誤，我們來驗證一下：

如果出現 ! ，則代表這個抽象操作 (abstract operation) 絕對不會丟出錯誤，例如步驟 14-a 的 ToString() 它會在參數是一個 Symbol 時丟出一個 TypeError，但我們確定丟進去的是一個 Number (F(k))，因此不會有丟出錯誤的可能。

從 ECMAScript 的演算法來看，尚未找到與 JavaScript 實作的不同之處。

利用 ECMAScript 製作客製化的 splice()

const array = [0, 1, 2, 3, 4, 5]
const removed = array.splice(1, 3, '*', '*')

console.log(array)
// [0, '*', '*', 4, 5]
console.log(removed)
// [1, 2, 3]


function splice(array, start, deleteCount, ...items) {
	const len = array.length
	const itemCount = items.length

	const removed = []

	let k = 0
	while (k < deleteCount) {
		const from = start + k
		removed.push(array[from])

		k++
	}

	// 當添加元素多於刪除元素，部分元素向左偏移
	if (itemCount < deleteCount) {
		k = start
		while(k < len - deleteCount) {
			const from = k + deleteCount
			const to = k + itemCount
			
			array[to] = array[from]
			k++
		}
		
		k = len
		while (k > (len - deleteCount + itemCount)) {
			array.pop()
			k--
		}
	}

	// 當添加元素多於刪除元素，部分元素向右偏移
	if (itemCount > deleteCount) {
		k = len - deleteCount
		while (k > start) {
			const from = k + deleteCount - 1
			const to = k + itemCount - 1

			array[to] = array[from]
			k --
		}
	}

	k = start
	items.forEach(element => {
		array[k] = element
		k++
	})
}

注意！這個客製化版本的 splice() 極其簡易，略過了非常多的步驟跟檢查，因此不是一個嚴謹好用的函式！這邊是想確定我們是否能利用 ECMAScript 所提供的演算法實作出一個咩色。

由於這個簡易版 splice() 並沒有做一些前置處理，所以在使用時必須提供 start 跟 delectCount，且其值不能為負數及小數。

結論

splice() 是一個很方便的咩色，但它會改動到原陣列，務必注意！

而 splice() 演算法較困難的地方落在了元素偏移的地方，個人覺得較為抽象，但可以試著理解看看！

最後，希望大家可以開心地使用各種咩色，體驗它帶給你的便利，祝大家歸剛沒煩惱。

參考資源

• Array.prototype.splice - MDN
• Draft ECMA 262 - TC39